The present invention relates to a technology effectively applicable to products and systems equipped with a security function such as IC cards, onboard microcomputer systems, and IOT (Internet of Things) in terms of countermeasures against a fault attack on the Chinese remainder theorem (CRT) used for the Rivest Shamir Adleman (RSA) algorithm as one of public key encryptions.
The RSA algorithm uses the Chinese remainder theorem for fast decryption. On the other hand, various attack techniques are proposed to expose secret information such as keys during execution of encryption algorithms such as RSA. A fault attack is one of dangerous attack techniques. This method generates an error using some technique during a calculation and specifies key information based on a result of this calculation and a result of the normal calculation.
RSA
The RSA algorithm uses equation X=ZemodM for encryption and equation Z=XfmodM for decryption, where e and ne denote public keys, f denotes a private key, Z denotes plain text, and X denotes encrypted text.
The following relations hold: 1=e×fmod{(p−1)(q−1)} and M=p×q, where p and q denote private prime numbers.
Chinese Remainder Theorem
When the above-mentioned decryption uses the Chinese remainder theorem, plain text Z results from the following equations: Dp=fmod (p−1); Dq=fmod(q−1); Xp=XDpmodp; Xq=XDqmodq; w=(Xp−Xq)×q−1modp; and Z=w×q+Xq.
Fault Attack
The fault attack technique exposes secret information such as a key by comparing a correct value with a value output from a faulty state caused by injecting a noise injected into a power supply or a clock or irradiating a laser to a circuit during encryption.
Fault Attack on the Chinese Remainder Theorem
As described below, a fault attack on the Chinese remainder theorem causes a faulty state during the modulo exponentiation operation to find Xp or Xq. The fault attack causes a faulty state at the timing to execute the modulo exponentiation operation to find Xp as illustrated in FIG. 6. Given Z′ denotes a calculation result to cause the faulty state and the error and Z denotes a correct calculation result, the following equations Z-Z′=(w-w′)×q and q=gcd{pq, (w-w′)×q}=gcd(M, Z-Z′) are used to find q as the greatest common divisor of known value M and output value difference Z-Z′. This can find p and f from q. An attacker can expose private key f.
Countermeasures Against the Fault Attack
The technique described in patent literature 1 provides a countermeasure against an attack technique that illegally exposes private key f by analyzing physical information such as power consumption. The technique described in patent literature 2 provides a countermeasure against an attack that analyzes power consumption or injects an error. However, none of the technologies consider countermeasures against a fault attack on the decryption algorithm using the Chinese remainder theorem. The inventors examined the following countermeasures.
The first countermeasure is to calculate Xp and Xq each twice and output value Z if the same value results from the calculations performed twice. If a recalculation yields different results, an attack is assumed to occur and value Z is not output. This method needs to perform the modulo exponentiation operation for Xp and Xq four times.
The second countermeasure is to re-encrypt result Z (X=ZemodM) of a calculation using the Chinese remainder theorem. Value Z is output if the result equals input X. Value Z is not output otherwise. It is common practice to use e=65537. In this case, the re-encryption does not require a long calculation time. The calculation time is not impractical.